#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>



typedef int BTTypeData;
typedef struct BinaryTree
{
	BTTypeData data;

	struct BinaryTree* left;
	struct BinaryTree* right;
}BinaryTree;



BinaryTree* BuyBinaryTree(BTTypeData x)
{
	BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BinaryTree* CreateBinaryTree()
{

	BinaryTree* node1 = BuyBinaryTree(1);
	BinaryTree* node2 = BuyBinaryTree(2);
	BinaryTree* node3 = BuyBinaryTree(3);
	BinaryTree* node4 = BuyBinaryTree(4);
	BinaryTree* node5 = BuyBinaryTree(5);
	BinaryTree* node6 = BuyBinaryTree(6);
	BinaryTree* node7 = BuyBinaryTree(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node3->right = node7;

	return node1;
}


void PreOrder(BinaryTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}


void InOrder(BinaryTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	
	PreOrder(root->left);
	printf("%d ", root->data);
	PreOrder(root->right);
}

void PostOrder(BinaryTree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}


	PreOrder(root->left);

	PreOrder(root->right);
	printf("%d ", root->data);

}


int TreeSize(BinaryTree* root)
{

	return root == 0 ? 0 : TreeSize(root->left) + TreeSize(root->left) + 1;
}

int TreeHeight(BinaryTree* root)
{
	if (root == 0)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);

	return left > right ? left + 1 : right + 1;

}

int TreeKLevel(BinaryTree* root,int k)
{
	
	if (root == 0)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return TreeKLevel(root->left,k-1) + TreeKLevel(root->right,k-1);
}

int main()
{
	BinaryTree* root = CreateBinaryTree();


	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");

	printf ("TreeSize : %d\n", TreeSize(root));
	
	printf("TreeHeight : %d\n", TreeHeight(root));

	printf("TreeKLevel : %d\n", TreeKLevel(root,3));
	

	return 0;
}
